<!DOCTYPE html>
            
<HTML>
<HEAD>
<meta name="booktitle" content="Developing Applications With Objective Caml" >
 <meta charset="ISO-8859-1"><meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0">
<META name="GENERATOR" content="hevea 1.05-7 of 2000-02-24">
<META NAME="Author" CONTENT="Christian.Queinnec@lip6.fr">
<LINK rel=stylesheet type="text/css" href="videoc-ocda.css">
<script language="JavaScript" src="videoc.js"><!--
//--></script>
<TITLE>
 Control Structures
</TITLE>
</HEAD>
<BODY class="regularBody">
<A HREF="book-ora027.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora029.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2> Control Structures</H2>
Input-output and modifiable values produce side-effects. Their use is
made easier by an imperative programming style furnished with new
control structures. We present in this section the sequence and
iteration structures.<BR>
<BR>
<A NAME="ex-if-then"></A>
We have already met the conditional control structure on page
<A HREF="book-ora015.html#subsec-cond">??</A>, whose abbreviated form <B>if</B> <B>then</B>
patterns itself on the imperative world. We will write, for
example: 


<PRE><BR># <B>let</B><CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE>ref<CODE> </CODE><CODE>1</CODE><CODE> </CODE>;;<BR><CODE>val n : int ref = {contents=1}</CODE><BR># <B>if</B><CODE> </CODE><CODE>!</CODE>n<CODE> </CODE><CODE>&gt;</CODE><CODE> </CODE><CODE>0</CODE><CODE> </CODE><B>then</B><CODE> </CODE>n<CODE> </CODE><CODE>:=</CODE><CODE> </CODE><CODE>!</CODE>n<CODE> </CODE><CODE>-</CODE><CODE> </CODE><CODE>1</CODE><CODE> </CODE>;;<BR><CODE>- : unit = ()</CODE><BR>

</PRE>
<BR>
<BR>
<A NAME="toc39"></A>
<H3> Sequence</H3>
<A NAME="@concepts107"></A>
<A NAME="@fonctions123"></A>
The first of the typically imperative structures is the
sequence. This permits the left-to-right evaluation of a
sequence of expressions separated by semicolons.


<H3> Syntax </H3> <HR>


 <I>expr</I><SUB><I><FONT SIZE=2>1</FONT></I></SUB> <B>;</B> ...<B>;</B> <I>expr</I><SUB><I><FONT SIZE=2><I>n</I></FONT></I></SUB>



<HR>


A sequence of expressions is itself an expression, whose value is that
of the last expression in the sequence (here, <I>expr</I><SUB><I><FONT SIZE=2><I>n</I></FONT></I></SUB>). Nevertheless, all the
expressions are evaluated, and in particular their side-effects are
taken into account.


<PRE><BR># print_string<CODE> </CODE><CODE>"2 = "</CODE>;<CODE> </CODE><CODE>1</CODE><CODE>+</CODE><CODE>1</CODE><CODE> </CODE>;;<BR><CODE>2 = - : int = 2</CODE><BR>

</PRE>
<BR>
<BR>
With side-effects, we get back the usual construction of imperative
languages. 


<PRE><BR># <B>let</B><CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE>ref<CODE> </CODE><CODE>1</CODE><CODE> </CODE>;;<BR><CODE>val x : int ref = {contents=1}</CODE><BR># x<CODE>:=!</CODE>x<CODE>+</CODE><CODE>1</CODE><CODE> </CODE>;<CODE> </CODE>x<CODE>:=!</CODE>x<CODE>*</CODE><CODE>4</CODE><CODE> </CODE>;<CODE> </CODE><CODE>!</CODE>x<CODE> </CODE>;;<BR><CODE>- : int = 8</CODE><BR>

</PRE>
<BR>
<BR>
As the value preceding a semicolon is discarded, Objective CAML gives a
warning when it is not of type <I>unit</I>.


<PRE><BR># print_int<CODE> </CODE><CODE>1</CODE>;<CODE> </CODE><CODE>2</CODE><CODE> </CODE>;<CODE> </CODE><CODE>3</CODE><CODE> </CODE>;;<BR><CODE>Characters 14-15:</CODE><BR><CODE>Warning: this expression should have type unit.</CODE><BR><CODE>1- : int = 3</CODE><BR>

</PRE>
<BR>
<BR>
<A NAME="@fonctions124"></A>
To avoid this message, you can use the function
<TT>ignore</TT>:


<PRE><BR># print_int<CODE> </CODE><CODE>1</CODE>;<CODE> </CODE>ignore<CODE> </CODE><CODE>2</CODE>;<CODE> </CODE><CODE>3</CODE><CODE> </CODE>;;<BR><CODE>1- : int = 3</CODE><BR>

</PRE>
<BR>
<BR>
A different message is obtained if the value has a functional type, as
Objective CAML suspects that you have forgotten a parameter of a function.


<PRE><BR># <B>let</B><CODE> </CODE>g<CODE> </CODE>x<CODE> </CODE>y<CODE> </CODE><CODE>=</CODE><CODE> </CODE>x<CODE> </CODE><CODE>:=</CODE><CODE> </CODE>y<CODE> </CODE>;;<BR><CODE>val g : 'a ref -&gt; 'a -&gt; unit = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>a<CODE> </CODE><CODE>=</CODE><CODE> </CODE>ref<CODE> </CODE><CODE>1</CODE><CODE>0</CODE>;;<BR><CODE>val a : int ref = {contents=10}</CODE><BR># <B>let</B><CODE> </CODE>u<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>1</CODE><CODE> </CODE><B>in</B><CODE> </CODE>g<CODE> </CODE>a<CODE> </CODE>;<CODE> </CODE>g<CODE> </CODE>a<CODE> </CODE>u<CODE> </CODE>;;<BR><CODE>Characters 13-16:</CODE><BR><CODE>Warning: this function application is partial,</CODE><BR><CODE>maybe some arguments are missing.</CODE><BR><CODE>- : unit = ()</CODE><BR># <B>let</B><CODE> </CODE>u<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>!</CODE>a<CODE> </CODE><B>in</B><CODE> </CODE>ignore<CODE> </CODE><TT>(</TT>g<CODE> </CODE>a<TT>)</TT><CODE> </CODE>;<CODE> </CODE>g<CODE> </CODE>a<CODE> </CODE>u<CODE> </CODE>;;<BR><CODE>- : unit = ()</CODE><BR>

</PRE>
<BR>
<BR>
As a general rule we parenthesize sequences to clarify their
scope. Syntactically, parenthesizing can take two forms:


<H3> Syntax </H3> <HR>

 <B>(</B> <I>expr</I> <B>)</B> 


<HR>




<H3> Syntax </H3> <HR>

 <B>begin</B> <I>expr</I> <B>end</B> 


<HR>


We can now write the Higher/Lower program from page <A HREF="book-ora027.html#cpcm">??</A> more
naturally: 


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>hilo<CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE>print_string<CODE> </CODE><CODE>"type a number: "</CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>i<CODE> </CODE><CODE>=</CODE><CODE> </CODE>read_int<CODE> </CODE>()<CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>i<CODE> </CODE><CODE>=</CODE><CODE> </CODE>n<CODE> </CODE><B>then</B><CODE> </CODE>print_string<CODE> </CODE><CODE>"BRAVO\n\n"</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>begin</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>i<CODE> </CODE><CODE>&lt;</CODE><CODE> </CODE>n<CODE> </CODE><B>then</B><CODE> </CODE>print_string<CODE> </CODE><CODE>"Higher\n"</CODE><CODE> </CODE><B>else</B><CODE> </CODE>print_string<CODE> </CODE><CODE>"Lower\n"</CODE><CODE> </CODE><CODE> </CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>hilo<CODE> </CODE>n<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>end</B><CODE> </CODE>;;<BR><CODE>val hilo : int -&gt; unit = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
<A NAME="toc40"></A>
<H3> Loops</H3>The iterative control structures are also from outside the functional
world. The conditional expression for repeating, or leaving, a loop does not make
sense unless there can be a physical modification of the memory which
permits its value to change. There are two iterative control
structures in Objective CAML: the <B>for</B> loop for a bounded iteration and the
<B>while</B> loop for a non-bounded iteration. The loop structures
themselves are expressions of the language. Thus they return a value:
the constant <B>()</B> of type <I>unit</I>.<BR>
<BR>
<A NAME="@fonctions125"></A>
<A NAME="@fonctions126"></A>
<A NAME="@fonctions127"></A>
<A NAME="@fonctions128"></A>
<A NAME="@fonctions129"></A>
The <B>for</B> loop can be rising (<B>to</B>) or falling
(<B>downto</B>) with a step of one.


<H3> Syntax </H3> <HR>


<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=left NOWRAP><B>for</B> <I>name</I> <B>=</B> <I>expr</I><SUB><I><FONT SIZE=2>1</FONT></I></SUB> <B>to</B>
 <I>expr</I><SUB><I><FONT SIZE=2>2</FONT></I></SUB> <B>do</B> <I>expr</I><SUB><I><FONT SIZE=2>3</FONT></I></SUB> <B>done</B></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP><B>for</B> <I>name</I> <B>=</B> <I>expr</I><SUB><I><FONT SIZE=2>1</FONT></I></SUB> <B>downto</B>
 <I>expr</I><SUB><I><FONT SIZE=2>2</FONT></I></SUB> <B>do</B> <I>expr</I><SUB><I><FONT SIZE=2>3</FONT></I></SUB> <B>done</B></TD>
</TR></TABLE>



<HR>

 
The expressions <I>expr</I><SUB><I><FONT SIZE=2>1</FONT></I></SUB> and <I>expr</I><SUB><I><FONT SIZE=2>2</FONT></I></SUB> are of type 
<I>int</I>. If <I>expr</I><SUB><I><FONT SIZE=2>3</FONT></I></SUB> is not of type <I>unit</I>, the compiler
produces a warning message.


<PRE><BR># <B>for</B><CODE> </CODE>i<CODE>=</CODE><CODE>1</CODE><CODE> </CODE><B>to</B><CODE> </CODE><CODE>1</CODE><CODE>0</CODE><CODE> </CODE><B>do</B><CODE> </CODE><CODE> </CODE>print_int<CODE> </CODE>i;<CODE> </CODE>print_string<CODE> </CODE><CODE>" "</CODE><CODE> </CODE><B>done</B>;<CODE> </CODE>print_newline()<CODE> </CODE>;;<BR><CODE>1 2 3 4 5 6 7 8 9 10 </CODE><BR><CODE>- : unit = ()</CODE><BR># <B>for</B><CODE> </CODE>i<CODE>=</CODE><CODE>1</CODE><CODE>0</CODE><CODE> </CODE><B>downto</B><CODE> </CODE><CODE>1</CODE><CODE> </CODE><B>do</B><CODE> </CODE>print_int<CODE> </CODE>i;<CODE> </CODE>print_string<CODE> </CODE><CODE>" "</CODE><CODE> </CODE><B>done</B>;<CODE> </CODE>print_newline()<CODE> </CODE>;;<BR><CODE>10 9 8 7 6 5 4 3 2 1 </CODE><BR><CODE>- : unit = ()</CODE><BR>

</PRE>
<BR>
<BR>
The non-bounded loop is the ``while'' loop whose syntax
is:
<A NAME="@fonctions130"></A> 


<H3> Syntax </H3> <HR>


 <B>while</B> <I>expr</I><SUB><I><FONT SIZE=2>1</FONT></I></SUB> <B>do</B> <I>expr</I><SUB><I><FONT SIZE=2>2</FONT></I></SUB> <B>done</B>



<HR>


The expression <I>expr</I><SUB><I><FONT SIZE=2>1</FONT></I></SUB> should be of type <I>bool</I>. And,
as for the <B>for</B> loop, if <I>expr</I><SUB><I><FONT SIZE=2>2</FONT></I></SUB> is not of type
<I>unit</I>, the compiler produces a warning message. 


<PRE><BR># <B>let</B><CODE> </CODE>r<CODE> </CODE><CODE>=</CODE><CODE> </CODE>ref<CODE> </CODE><CODE>1</CODE><CODE> </CODE><BR><CODE> </CODE><B>in</B><CODE> </CODE><B>while</B><CODE> </CODE><CODE>!</CODE>r<CODE> </CODE><CODE>&lt;</CODE><CODE> </CODE><CODE>1</CODE><CODE>1</CODE><CODE> </CODE><CODE> </CODE><B>do</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>print_int<CODE> </CODE><CODE>!</CODE>r<CODE> </CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>print_string<CODE> </CODE><CODE>" "</CODE><CODE> </CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>r<CODE> </CODE><CODE>:=</CODE><CODE> </CODE><CODE>!</CODE>r<CODE>+</CODE><CODE>1</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>done</B><CODE> </CODE>;;<BR><CODE>1 2 3 4 5 6 7 8 9 10 - : unit = ()</CODE><BR>

</PRE>
<BR>
<BR>
It is important to understand that loops are expressions like the
previous ones which calculate the value <B>()</B> of type <I>unit</I>.


<PRE><BR># <B>let</B><CODE> </CODE>f<CODE> </CODE>()<CODE> </CODE><CODE>=</CODE><CODE> </CODE>print_string<CODE> </CODE><CODE>"-- end\n"</CODE><CODE> </CODE>;;<BR><CODE>val f : unit -&gt; unit = &lt;fun&gt;</CODE><BR># f<CODE> </CODE><TT>(</TT><B>for</B><CODE> </CODE>i<CODE>=</CODE><CODE>1</CODE><CODE> </CODE><B>to</B><CODE> </CODE><CODE>1</CODE><CODE>0</CODE><CODE> </CODE><B>do</B><CODE> </CODE><CODE> </CODE>print_int<CODE> </CODE>i;<CODE> </CODE>print_string<CODE> </CODE><CODE>" "</CODE><CODE> </CODE><B>done</B><TT>)</TT><CODE> </CODE>;;<BR><CODE>1 2 3 4 5 6 7 8 9 10 -- end</CODE><BR><CODE>- : unit = ()</CODE><BR>

</PRE>

Note that the string <CODE>"-- end\n"</CODE> is output after
the integers from 1 to 10 have been printed: this is a demonstration
that the arguments (here the loop) are evaluated before being
passed to the function.<BR>
<BR>
In imperative programming, the body of a loop (<I>expr</I><SUB><I><FONT SIZE=2>2</FONT></I></SUB>) 
does not calculate a value, but advances by side
effects. In Objective CAML, when the body of a loop is not of type
<I>unit</I> the compiler prints a warning, as for the sequence:


<PRE><BR># <B>let</B><CODE> </CODE>s<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>[</CODE><CODE>5</CODE>;<CODE> </CODE><CODE>4</CODE>;<CODE> </CODE><CODE>3</CODE>;<CODE> </CODE><CODE>2</CODE>;<CODE> </CODE><CODE>1</CODE>;<CODE> </CODE><CODE>0</CODE><CODE>]</CODE><CODE> </CODE>;;<CODE> </CODE><BR><CODE>val s : int list = [5; 4; 3; 2; 1; 0]</CODE><BR># <CODE> </CODE><B>for</B><CODE> </CODE>i<CODE>=</CODE><CODE>0</CODE><CODE> </CODE><B>to</B><CODE> </CODE><CODE>5</CODE><CODE> </CODE><B>do</B><CODE> </CODE>List.tl<CODE> </CODE>s<CODE> </CODE><B>done</B><CODE> </CODE>;;<BR><CODE>Characters 17-26:</CODE><BR><CODE>Warning: this expression should have type unit.</CODE><BR><CODE>- : unit = ()</CODE><BR>

</PRE>
<BR>
<BR>
<A NAME="toc41"></A>
<H3> Example: Implementing a Stack</H3><A NAME="ex-pile"></A>
The data structure <I>'a stack</I> will be implemented in the form
of a record containing an array of elements and the first free
position in this array. Here is the corresponding type:


<PRE><BR># <B>type</B><CODE> </CODE><I>'a</I><CODE> </CODE>stack<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE><B>mutable</B><CODE> </CODE>ind<CODE>:</CODE>int;<CODE> </CODE>size<CODE>:</CODE>int;<CODE> </CODE><B>mutable</B><CODE> </CODE>elts<CODE> </CODE><CODE>:</CODE><CODE> </CODE><I>'a</I><CODE> </CODE>array<CODE> </CODE>}<CODE> </CODE>;;<BR>

</PRE>

The field <TT>size</TT> contains the maximal size of the stack.<BR>
<BR>
The operations on these stacks will be <TT>init_stack</TT> for the
initialization of a stack, <TT>push</TT> for pushing an element onto a
stack, and <TT>pop</TT> for returning the top of the stack and popping
it off.


<PRE><BR># <B>let</B><CODE> </CODE>init_stack<CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{ind<CODE>=</CODE><CODE>0</CODE>;<CODE> </CODE>size<CODE>=</CODE>n;<CODE> </CODE>elts<CODE> </CODE><CODE>=[||]}</CODE><CODE> </CODE>;;<BR><CODE>val init_stack : int -&gt; 'a stack = &lt;fun&gt;</CODE><BR>

</PRE>

This function cannot create a non-empty array, because you would have
to provide it with the value with which to construct it. This is why
the field <TT>elts</TT> gets an empty array.<BR>
<BR>
Two exceptions are declared to guard against attempts to pop an empty 
stack or to add an element to a full stack. They are used in the
functions <TT>pop</TT> and <TT>push</TT>.


<PRE><BR># <B>exception</B><CODE> </CODE>Stack_empty<CODE> </CODE>;;<BR># <B>exception</B><CODE> </CODE>Stack_full<CODE> </CODE>;;<BR><BR># <B>let</B><CODE> </CODE>pop<CODE> </CODE>p<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>p<CODE>.</CODE>ind<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>0</CODE><CODE> </CODE><B>then</B><CODE> </CODE>raise<CODE> </CODE>Stack_empty<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><TT>(</TT>p<CODE>.</CODE>ind<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>p<CODE>.</CODE>ind<CODE> </CODE><CODE>-</CODE><CODE> </CODE><CODE>1</CODE>;<CODE> </CODE>p<CODE>.</CODE>elts<CODE>.</CODE><TT>(</TT>p<CODE>.</CODE>ind<TT>)</TT><TT>)</TT><CODE> </CODE>;;<BR><CODE>val pop : 'a stack -&gt; 'a = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>push<CODE> </CODE>e<CODE> </CODE>p<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>p<CODE>.</CODE>elts<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>[||]</CODE><CODE> </CODE><B>then</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><TT>(</TT>p<CODE>.</CODE>elts<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>Array.create<CODE> </CODE>p<CODE>.</CODE>size<CODE> </CODE>e;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>p<CODE>.</CODE>ind<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE><CODE>1</CODE><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><B>if</B><CODE> </CODE>p<CODE>.</CODE>ind<CODE> </CODE><CODE>&gt;=</CODE><CODE> </CODE>p<CODE>.</CODE>size<CODE> </CODE><B>then</B><CODE> </CODE>raise<CODE> </CODE>Stack_full<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><TT>(</TT>p<CODE>.</CODE>elts<CODE>.</CODE><TT>(</TT>p<CODE>.</CODE>ind<TT>)</TT><CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>e;<CODE> </CODE>p<CODE>.</CODE>ind<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>p<CODE>.</CODE>ind<CODE> </CODE><CODE>+</CODE><CODE> </CODE><CODE>1</CODE><TT>)</TT><CODE> </CODE>;;<BR><CODE>val push : 'a -&gt; 'a stack -&gt; unit = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
Here is a small example of the use of this data structure:


<PRE><BR># <B>let</B><CODE> </CODE>p<CODE> </CODE><CODE>=</CODE><CODE> </CODE>init_stack<CODE> </CODE><CODE>4</CODE><CODE> </CODE>;;<BR><CODE>val p : '_a stack = {ind=0; size=4; elts=[||]}</CODE><BR># push<CODE> </CODE><CODE>1</CODE><CODE> </CODE>p<CODE> </CODE>;;<BR><CODE>- : unit = ()</CODE><BR># <B>for</B><CODE> </CODE>i<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>2</CODE><CODE> </CODE><B>to</B><CODE> </CODE><CODE>5</CODE><CODE> </CODE><B>do</B><CODE> </CODE>push<CODE> </CODE>i<CODE> </CODE>p<CODE> </CODE><B>done</B><CODE> </CODE>;;<BR><CODE>Uncaught exception: Stack_full</CODE><BR># p<CODE> </CODE>;;<BR><CODE>- : int stack = {ind=4; size=4; elts=[|1; 2; 3; 4|]}</CODE><BR># pop<CODE> </CODE>p<CODE> </CODE>;;<BR><CODE>- : int = 4</CODE><BR># pop<CODE> </CODE>p<CODE> </CODE>;;<BR><CODE>- : int = 3</CODE><BR>

</PRE>
<BR>
<BR>
If we want to prevent raising the exception <TT>Stack_full</TT> when
attempting to add an element to the stack, we can enlarge the
array. To do this the field <TT>size</TT> must be modifiable too:


<PRE><BR># <B>type</B><CODE> </CODE><I>'a</I><CODE> </CODE>stack<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE>{<B>mutable</B><CODE> </CODE>ind<CODE>:</CODE>int<CODE> </CODE>;<CODE> </CODE><B>mutable</B><CODE> </CODE>size<CODE>:</CODE>int<CODE> </CODE>;<CODE> </CODE><B>mutable</B><CODE> </CODE>elts<CODE> </CODE><CODE>:</CODE><CODE> </CODE><I>'a</I><CODE> </CODE>array}<CODE> </CODE>;;<BR># <B>let</B><CODE> </CODE>init_stack<CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{ind<CODE>=</CODE><CODE>0</CODE>;<CODE> </CODE>size<CODE>=</CODE>max<CODE> </CODE>n<CODE> </CODE><CODE>1</CODE>;<CODE> </CODE>elts<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>[||]}</CODE><CODE> </CODE>;;<BR># <B>let</B><CODE> </CODE>n_push<CODE> </CODE>e<CODE> </CODE>p<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>p<CODE>.</CODE>elts<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>[||]</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>then</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>begin</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>p<CODE>.</CODE>elts<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>Array.create<CODE> </CODE>p<CODE>.</CODE>size<CODE> </CODE>e;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>p<CODE>.</CODE>ind<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE><CODE>1</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>end</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><B>if</B><CODE> </CODE>p<CODE>.</CODE>ind<CODE> </CODE><CODE>&gt;=</CODE><CODE> </CODE>p<CODE>.</CODE>size<CODE> </CODE><B>then</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>begin</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>nt<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>2</CODE><CODE> </CODE><CODE>*</CODE><CODE> </CODE>p<CODE>.</CODE>size<CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>nv<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Array.create<CODE> </CODE>nt<CODE> </CODE>e<CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>for</B><CODE> </CODE>j<CODE>=</CODE><CODE>0</CODE><CODE> </CODE><B>to</B><CODE> </CODE>p<CODE>.</CODE>size<CODE>-</CODE><CODE>1</CODE><CODE> </CODE><B>do</B><CODE> </CODE>nv<CODE>.</CODE><TT>(</TT>j<TT>)</TT><CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>p<CODE>.</CODE>elts<CODE>.</CODE><TT>(</TT>j<TT>)</TT><CODE> </CODE><B>done</B><CODE> </CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>p<CODE>.</CODE>elts<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>nv;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>p<CODE>.</CODE>size<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>nt;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>p<CODE>.</CODE>ind<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>p<CODE>.</CODE>ind<CODE> </CODE><CODE>+</CODE><CODE> </CODE><CODE>1</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>end</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>begin</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>p<CODE>.</CODE>elts<CODE>.</CODE><TT>(</TT>p<CODE>.</CODE>ind<TT>)</TT><CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>e<CODE> </CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>p<CODE>.</CODE>ind<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>p<CODE>.</CODE>ind<CODE> </CODE><CODE>+</CODE><CODE> </CODE><CODE>1</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>end</B><CODE> </CODE>;;<BR><CODE>val n_push : 'a -&gt; 'a stack -&gt; unit = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
All the same, you have to be careful with data structures which can
expand without bound. Here is a small example where
the initial stack grows as needed.


<PRE><BR># <B>let</B><CODE> </CODE>p<CODE> </CODE><CODE>=</CODE><CODE> </CODE>init_stack<CODE> </CODE><CODE>4</CODE><CODE> </CODE>;;<BR><CODE>val p : '_a stack = {ind=0; size=4; elts=[||]}</CODE><BR># <B>for</B><CODE> </CODE>i<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>1</CODE><CODE> </CODE><B>to</B><CODE> </CODE><CODE>5</CODE><CODE> </CODE><B>do</B><CODE> </CODE>n_push<CODE> </CODE>i<CODE> </CODE>p<CODE> </CODE><B>done</B><CODE> </CODE>;;<BR><CODE>- : unit = ()</CODE><BR># p<CODE> </CODE>;;<BR><CODE>- : int stack = {ind=5; size=8; elts=[|1; 2; 3; 4; 5; 5; 5; 5|]}</CODE><BR># p<CODE>.</CODE>stack<CODE> </CODE>;;<BR><CODE>Characters 0-7:</CODE><BR><CODE>Unbound label stack</CODE><BR>

</PRE>
<BR>
<BR>
It might also be useful to allow <TT>pop</TT> to decrease the size of
the stack, to reclaim unused memory.<BR>
<BR>
<A NAME="toc42"></A>
<H3> Example: Calculations on Matrices</H3>
In this example we aim to define a type for matrices, two-dimensional
arrays containing floating point numbers, and to write some operations
on the matrices. The monomorphic type <I>mat</I> is a record
containing the dimensions and the elements of the matrix. The
functions <TT>create_mat</TT>, <TT>access_mat</TT>, and
<TT>mod_mat</TT> are respectively the functions for creation,
accessing an element, and modification of an element.


<PRE><BR># <B>type</B><CODE> </CODE>mat<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>n<CODE>:</CODE>int;<CODE> </CODE>m<CODE>:</CODE>int;<CODE> </CODE>t<CODE>:</CODE><CODE> </CODE>float<CODE> </CODE>array<CODE> </CODE>array<CODE> </CODE>};;<BR><CODE>type mat = { n: int; m: int; t: float array array }</CODE><BR># <B>let</B><CODE> </CODE>create_mat<CODE> </CODE>n<CODE> </CODE>m<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>n<CODE>=</CODE>n;<CODE> </CODE>m<CODE>=</CODE>m;<CODE> </CODE>t<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Array.create_matrix<CODE> </CODE>n<CODE> </CODE>m<CODE> </CODE><CODE>0</CODE><CODE>.</CODE><CODE>0</CODE><CODE> </CODE>}<CODE> </CODE>;;<BR><CODE>val create_mat : int -&gt; int -&gt; mat = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>access_mat<CODE> </CODE>m<CODE> </CODE>i<CODE> </CODE>j<CODE> </CODE><CODE>=</CODE><CODE> </CODE>m<CODE>.</CODE>t<CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE>.</CODE><TT>(</TT>j<TT>)</TT><CODE> </CODE>;;<BR><CODE>val access_mat : mat -&gt; int -&gt; int -&gt; float = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>mod_mat<CODE> </CODE>m<CODE> </CODE>i<CODE> </CODE>j<CODE> </CODE>e<CODE> </CODE><CODE>=</CODE><CODE> </CODE>m<CODE>.</CODE>t<CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE>.</CODE><TT>(</TT>j<TT>)</TT><CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>e<CODE> </CODE>;;<BR><CODE>val mod_mat : mat -&gt; int -&gt; int -&gt; float -&gt; unit = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>a<CODE> </CODE><CODE>=</CODE><CODE> </CODE>create_mat<CODE> </CODE><CODE>3</CODE><CODE> </CODE><CODE>3</CODE><CODE> </CODE>;;<BR><CODE>val a : mat = {n=3; m=3; t=[|[|0; 0; 0|]; [|0; 0; 0|]; [|0; 0; 0|]|]}</CODE><BR># mod_mat<CODE> </CODE>a<CODE> </CODE><CODE>1</CODE><CODE> </CODE><CODE>1</CODE><CODE> </CODE><CODE>2</CODE><CODE>.</CODE><CODE>0</CODE>;<CODE> </CODE>mod_mat<CODE> </CODE>a<CODE> </CODE><CODE>1</CODE><CODE> </CODE><CODE>2</CODE><CODE> </CODE><CODE>1</CODE><CODE>.</CODE><CODE>0</CODE>;<CODE> </CODE>mod_mat<CODE> </CODE>a<CODE> </CODE><CODE>2</CODE><CODE> </CODE><CODE>1</CODE><CODE> </CODE><CODE>1</CODE><CODE>.</CODE><CODE>0</CODE><CODE> </CODE>;;<BR><CODE>- : unit = ()</CODE><BR># a<CODE> </CODE>;;<BR><CODE>- : mat = {n=3; m=3; t=[|[|0; 0; 0|]; [|0; 2; 1|]; [|0; 1; 0|]|]}</CODE><BR>

</PRE>
<BR>
<BR>
The sum of two matrices <I>a</I> and <I>b</I> is a matrix <I>c</I>&nbsp; such that
&nbsp;&nbsp;<I>c</I><SUB><FONT SIZE=2><I>ij</I></FONT></SUB> = <I>a</I><SUB><FONT SIZE=2><I>ij</I></FONT></SUB> + <I>b</I><SUB><FONT SIZE=2><I>ij</I></FONT></SUB>.


<PRE><BR># <B>let</B><CODE> </CODE>add_mat<CODE> </CODE>p<CODE> </CODE>q<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>p<CODE>.</CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE>q<CODE>.</CODE>n<CODE> </CODE><CODE>&amp;&amp;</CODE><CODE> </CODE>p<CODE>.</CODE>m<CODE> </CODE><CODE>=</CODE><CODE> </CODE>q<CODE>.</CODE>m<CODE> </CODE><B>then</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>r<CODE> </CODE><CODE>=</CODE><CODE> </CODE>create_mat<CODE> </CODE>p<CODE>.</CODE>n<CODE> </CODE>p<CODE>.</CODE>m<CODE> </CODE><CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>for</B><CODE> </CODE>i<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>0</CODE><CODE> </CODE><B>to</B><CODE> </CODE>p<CODE>.</CODE>n<CODE>-</CODE><CODE>1</CODE><CODE> </CODE><B>do</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>for</B><CODE> </CODE>j<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>0</CODE><CODE> </CODE><B>to</B><CODE> </CODE>p<CODE>.</CODE>m<CODE>-</CODE><CODE>1</CODE><CODE> </CODE><B>do</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>mod_mat<CODE> </CODE>r<CODE> </CODE>i<CODE> </CODE>j<CODE> </CODE><CODE> </CODE><TT>(</TT>p<CODE>.</CODE>t<CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE>.</CODE><TT>(</TT>j<TT>)</TT><CODE> </CODE><CODE>+.</CODE><CODE> </CODE>q<CODE>.</CODE>t<CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE>.</CODE><TT>(</TT>j<TT>)</TT><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>done</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>done</B><CODE> </CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>r<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE>failwith<CODE> </CODE><CODE>"add_mat : dimensions incompatible"</CODE>;;<CODE> </CODE><BR><CODE>val add_mat : mat -&gt; mat -&gt; mat = &lt;fun&gt;</CODE><BR># add_mat<CODE> </CODE><CODE> </CODE>a<CODE> </CODE>a<CODE> </CODE>;;<BR><CODE>- : mat = {n=3; m=3; t=[|[|0; 0; 0|]; [|0; 4; 2|]; [|0; 2; 0|]|]}</CODE><BR>

</PRE>
<BR>
<BR>
The product of two matrices <I>a</I> and <I>b</I> is a matrix <I>c</I>&nbsp; such that
<I>c</I><SUB><FONT SIZE=2><I>ij</I></FONT></SUB> = <FONT FACE=symbol>�</FONT><SUB><FONT SIZE=2><I>k</I>=1</FONT></SUB><SUP><FONT SIZE=2><I>k</I>=<I>m</I></FONT></SUP><SUB><SUP><FONT SIZE=2><I>a</I></FONT></SUP></SUB> <I>a</I><SUB><FONT SIZE=2><I>ik</I></FONT></SUB>. <I>b</I><SUB><FONT SIZE=2><I>kj</I></FONT></SUB> 


<PRE><BR># <B>let</B><CODE> </CODE>mul_mat<CODE> </CODE>p<CODE> </CODE>q<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>p<CODE>.</CODE>m<CODE> </CODE><CODE>=</CODE><CODE> </CODE>q<CODE>.</CODE>n<CODE> </CODE><B>then</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>r<CODE> </CODE><CODE>=</CODE><CODE> </CODE>create_mat<CODE> </CODE>p<CODE>.</CODE>n<CODE> </CODE>q<CODE>.</CODE>m<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>for</B><CODE> </CODE>i<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>0</CODE><CODE> </CODE><B>to</B><CODE> </CODE>p<CODE>.</CODE>n<CODE>-</CODE><CODE>1</CODE><CODE> </CODE><B>do</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>for</B><CODE> </CODE>j<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>0</CODE><CODE> </CODE><B>to</B><CODE> </CODE>q<CODE>.</CODE>m<CODE>-</CODE><CODE>1</CODE><CODE> </CODE><B>do</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>c<CODE> </CODE><CODE>=</CODE><CODE> </CODE>ref<CODE> </CODE><CODE>0</CODE><CODE>.</CODE><CODE>0</CODE><CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>for</B><CODE> </CODE>k<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>0</CODE><CODE> </CODE><B>to</B><CODE> </CODE>p<CODE>.</CODE>m<CODE>-</CODE><CODE>1</CODE><CODE> </CODE><B>do</B><CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>c<CODE> </CODE><CODE>:=</CODE><CODE> </CODE><CODE>!</CODE>c<CODE> </CODE><CODE>+.</CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><TT>(</TT>p<CODE>.</CODE>t<CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE>.</CODE><TT>(</TT>k<TT>)</TT><CODE> </CODE><CODE>*.</CODE><CODE> </CODE>q<CODE>.</CODE>t<CODE>.</CODE><TT>(</TT>k<TT>)</TT><CODE>.</CODE><TT>(</TT>j<TT>)</TT><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>done</B>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>mod_mat<CODE> </CODE>r<CODE> </CODE>i<CODE> </CODE>j<CODE> </CODE><CODE>!</CODE>c<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>done</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>done</B>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>r<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE>failwith<CODE> </CODE><CODE>"mul_mat : dimensions incompatible"</CODE><CODE> </CODE>;;<CODE> </CODE><BR><CODE>val mul_mat : mat -&gt; mat -&gt; mat = &lt;fun&gt;</CODE><BR># mul_mat<CODE> </CODE>a<CODE> </CODE>a;;<BR><CODE>- : mat = {n=3; m=3; t=[|[|0; 0; 0|]; [|0; 5; 2|]; [|0; 2; 1|]|]}</CODE><BR>

</PRE>
<BR>
<BR>
<HR>
<A HREF="book-ora027.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora029.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
